package com.example.zzy.zzytest.data.structure.list.singlelinkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");

        SingleLinkedList list = new SingleLinkedList();
        list.add(heroNode1);
        list.add(heroNode3);
        list.add(heroNode4);
        list.addByOrder(heroNode2);

        System.out.println("反向输出");
        list.reverseShow();

        System.out.println("原始------");
        list.show();
        System.out.println("反转------");
        list.reverse();
        list.show();
        System.out.println("\n");
        System.out.println("再反转------");
        list.reverse();
        list.show();
        System.out.println("\n");


//        System.out.println("长度>>>" + list.getLength());
//        System.out.println("倒数第1>>>" + list.findLastIndexNode(1));
//        System.out.println("倒数第2>>>" + list.findLastIndexNode(2));
//        System.out.println("\n");
//
//        list.update(new HeroNode(2, "鲁智深俊逸", "花姑娘"));
//        list.show();
//        System.out.println("\n");
//
//        list.del(4);
//        list.del(2);
//        list.show();
//        System.out.println("倒数第1>>>" + list.findLastIndexNode(1));
//        System.out.println("倒数第2>>>" + list.findLastIndexNode(2));
//        System.out.println("\n");

    }
}


class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

class SingleLinkedList {
    //头结点不动，不放具体值
    private HeroNode head = new HeroNode(0, "", "");

    //插入到最后
    public void add(HeroNode node) {
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                temp.next = node;
                break;
            }
            temp = temp.next;
        }
    }

    //根据编号插入
    public void addByOrder(HeroNode node) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            //位置到达最后退出
            if (temp.next == null) {
                break;
            }
            //temp的下个节点值大于待插入node，则在temp后插入
            if (temp.next.no > node.no) {
                break;
            } else if (temp.next.no == node.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            System.out.println("当前no已存在，插入失败");
        } else {
            node.next = temp.next;
            temp.next = node;
        }
    }

    //修改
    public void update(HeroNode node) {
        HeroNode temp = head.next;

        while (true) {
            if (temp == null) {
                System.out.println("遍历结束，没有找到该节点");
                return;
            }
            if (temp.no == node.no) {
                temp.name = node.name;
                temp.nickName = node.nickName;
                break;
            }

            temp = temp.next;
        }
    }

    //删除
    public void del(int no) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            //到了末尾
            if (temp.next == null) {
                break;
            }
            //找到，可以删除
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到待删除的节点");
        }
    }

    //显示
    public void show() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //获取节点个数
    public int getLength() {
        if (head.next == null) {
            return 0;
        }
        int len = 0;
        HeroNode temp = head.next;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        return len;
    }

    //单向链表获取倒数第k个节点
    public HeroNode findLastIndexNode(int index) {
        int len = getLength();
        if (index <= 0 || index > len) {
            return null;
        }
        HeroNode temp = head.next;
        for (int i = 0; i < len; i++) {
            if (i == len - index) {
                break;
            }
            temp = temp.next;
        }
        return temp;
    }

    //反转
    public void reverse() {
        //如果只包含头节点或头结点后只有一个节点，则没必要反转
        if (head.next == null || head.next.next == null) {
            return;
        }
        //遍历原链表，所有遍历到的元素加入到新链表的头部
        HeroNode cur = head.next;
        HeroNode next = null;//指向cur的下一个，用来保存cur遍历的位置
        HeroNode reverseHead = new HeroNode(0, "", "");

        while (cur != null) {
            //首先保存cur的下一次遍历需要在的位置，因为一会cur会被插到head后
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }

        head.next = reverseHead.next;
    }

    /**
     * 从尾到头遍历
     * 方式1：先反转，在遍历，在反转
     * 方式2：stack
     */
    public void reverseShow() {
        if (head.next == null) {
            return;
        }
        Stack<HeroNode> nodeStack = new Stack<>();
        HeroNode temp = head.next;
        while (temp != null) {
            nodeStack.push(temp);
            temp = temp.next;
        }
        while (!nodeStack.empty()) {
            System.out.println(nodeStack.pop());
        }
    }
}
